﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0081)http://www.realintelligence.net/tutorials.php?category=optim&tutName=geneticalgos -->
<HTML xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>The Real Intelligence Project - Genetic algorithms tutorial</TITLE><!-- InstanceBegin template="/Templates/mainSiteTemplate.dwt.php" codeOutsideHTMLIsLocked="false" -->
<META http-equiv=Content-Type content="text/html; charset=utf-8"><!--[if lte IE 6]>
<SCRIPT 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/supersleight.js" 
type=text/javascript></SCRIPT>
<![endif]--><LINK 
href="The Real Intelligence Project - Genetic algorithms tutorial.files/mainStyle.css" 
type=text/css rel=stylesheet>
<SCRIPT 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/menuAnim2.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/mootools.svn.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/menuAnim1.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/onLoad.js" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>
if(screen.width <=840)
{
	var headID = document.getElementsByTagName("head")[0];     
var cssNode = document.createElement('link');
cssNode.type = 'text/css';
cssNode.rel = 'stylesheet';
cssNode.href = '/CSS/res800.css';
cssNode.media = 'screen';
headID.appendChild(cssNode);
}
else if(screen.width > 840 && screen.width <=1050)
{
	var headID = document.getElementsByTagName("head")[0];     
var cssNode = document.createElement('link');
cssNode.type = 'text/css';
cssNode.rel = 'stylesheet';
cssNode.href = '/CSS/res1000.css';
cssNode.media = 'screen';
headID.appendChild(cssNode);
}
else if(screen.width > 1050 && screen.width <=1300)
{
	var headID = document.getElementsByTagName("head")[0];     
var cssNode = document.createElement('link');
cssNode.type = 'text/css';
cssNode.rel = 'stylesheet';
cssNode.href = '/CSS/res1200.css';
cssNode.media = 'screen';
headID.appendChild(cssNode);
}
else if(screen.width > 1300 && screen.width <=1450)
{
	var headID = document.getElementsByTagName("head")[0];     
var cssNode = document.createElement('link');
cssNode.type = 'text/css';
cssNode.rel = 'stylesheet';
cssNode.href = '/CSS/res1400.css';
cssNode.media = 'screen';
headID.appendChild(cssNode);
}

</SCRIPT>
<!-- Google analytics code -->
<SCRIPT type=text/javascript>
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</SCRIPT>

<SCRIPT type=text/javascript>
try {
var pageTracker = _gat._getTracker("UA-9200591-1");
pageTracker._trackPageview();
} catch(err) {}</SCRIPT>
<!-- Google analytics code ends -->
<META content="MSHTML 6.00.2900.5880" name=GENERATOR></HEAD>
<BODY onload=onLoad()>
<DIV id=pageHead><IMG class=logo id=logo 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/logo4.png"></DIV>
<DIV id=leftMenu>
<H3 class="toggler menusection" 
onmouseover="this.style.cursor='pointer'">Current Projects</H3>
<DIV class="element menusection">
<UL>
  <LI><A 
  href="http://www.realintelligence.net/projects.php?prName=neuroevolution">Research 
  on neural networks and genetic algorithms</A> </LI></UL></DIV>
<H3 class="toggler menusection" onmouseover="this.style.cursor='pointer'">Past 
Projects</H3>
<DIV class="element menusection">
<UL>
  <LI><A href="http://www.realintelligence.net/projects.php?prName=mazebot">The 
  Mazebot Project</A> 
  <LI><A 
  href="http://www.realintelligence.net/projects.php?prName=floatemu">Floating 
  point emulation on embedded devices</A> </LI></UL></DIV>
<H3 class="toggler menusection" 
onmouseover="this.style.cursor='pointer'">Tutorials</H3>
<DIV class="element menusection">
<UL>
  <LI><A 
  href="http://www.realintelligence.net/tutorials.php?category=ann">Neural 
  Networks</A> 
  <LI><A 
  href="http://www.realintelligence.net/tutorials.php?category=optim">Search and 
  Optimization</A> 
  <LI><A 
  href="http://www.realintelligence.net/tutorials.php?category=programming">Programming</A> 
  </LI></UL></DIV>
<H3 class="toggler menusection" onmouseover="this.style.cursor='pointer'">About 
the Author</H3>
<DIV class="element menusection">
<UL>
  <LI><A href="http://www.realintelligence.net/bio.php?reason=CV">CV</A> 
  <LI><A href="http://www.realintelligence.net/bio.php?reason=thoughts">A few 
  words about me</A> </LI></UL></DIV></DIV>
<DIV id=centerContainer>
<DIV id=tabMenu>
<UL>
  <LI><A href="http://www.realintelligence.net/index.php"><SPAN>
  <H1>Home</H1></SPAN></A>
  <LI><A href="http://www.realintelligence.net/faq.php"><SPAN>
  <H1>Frequently Asked Questions</H1></SPAN></A>
  <LI><A href="http://lefteris.realintelligence.net/"><SPAN>
  <H1>A blog</H1></SPAN></A>
  <LI><A href="http://www.realintelligence.net/about.php"><SPAN>
  <H1>About</H1></SPAN></A>
  <LI id=current><A href="http://www.realintelligence.net/tutorials.php"><SPAN>
  <H1>Tutorials</H1></SPAN></A></LI></UL></DIV>
<DIV id=centerWrapper>
<DIV id=leftTCorner></DIV>
<DIV id=topWrapper></DIV>
<DIV id=rightTCorner></DIV>
<DIV id=leftWrapper>
<DIV id=rightWrapper>
<DIV id=centerOfPage><!-- InstanceBeginEditable name="head" -->
<H2>An introduction to genetic algorithms</H2>
<P class=content>This tutorial introduces the reader to genetic algorithms. They 
are algorithms based on the theory of evolution and are applied as optimization 
techniques in various fields. The tutorial will make a small introduction to how 
genetic algorithms work and the theory behind them and then back it up with an 
example program of trying to evolve a solution for a sudoku puzzle. The tutorial 
source code can be found <A 
href="http://www.realintelligence.net/Files/GeneticAlgosTutorial.zip">here</A>, 
but to understand how it works it would be good to read on and see what each 
line of code does. </P>
<P class=content>
<H4>Tutorial Prerequisities</H4>
<LI>The reader should have a basic understanding of C/C++ 
<LI>The reader should know how to compile and run a program using any of the 
popular C compilers 
<P></P>
<P class=content>
<H4>Tutorial Goals</H4>
<LI>The reader will understand what geenetic algorithms are and why they 
actually work 
<LI>The reader will see how we can evolve solutions to problems by watching a 
sudoku solution evolve itself. 
<P></P><BR><BR><BR>
<H4>Tutorial Body</H4>
<P class=content>In this tutorial we will see what genetic algorithms are, how 
they work and the theory behing their operation. Moreover we will see an example 
of using genetic algorithms to solve sudoku puzzles. As always the usual 
disclaimer applies. I can not promise that this is the best implementation of a 
genetic algorithm or a sudoku solver but it is enough to let someone understand 
how to create one himself and to provide a good understanding of genetic 
algorithms. </P>
<P class=content>Genetic algorithms are based on the theory of evolution, the 
theory which dominates nature and allows for the improvement of species in order 
to better adopt to their environment. Evolution works with the famous mechanisms 
of natural selection and survival of the fittest. We can not even question the 
efficiency of that mechanism, the results are all around us, even you and me. So 
why not try to create an algorithm which will use that efficient mechanism? 
That's why genetic algorithms were created.</P>
<P class=content><IMG id=rightFloat 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/chromosome.png" 
width="60%">What is particularly interesting though is the way genetic 
algorithms mimick this mechanism of nature to solve problems, problems of any 
mangitude. The way they do it is by representing each potential solution with a 
chromosome as can be seen in the right. A chromosome is a potential solution to 
the problem at hand. For example the perfect course schedule for an academic 
institution. The chromosome is usually an array of bytes like the one on the 
right but it can also be a matrix or even a graph! For our course schedule 
program the chromosome could contain the datestamp of the lesson, the teacher 
and the nature of the class in 3 bytes. Then the whole schedule could be an 
array of these 3 type of bytes repeating themselves. What the genetic algorithm 
actually does then is initialise a population of these potential solutions, 
these chromosomes. The bigger the population, the better for us since there is 
more genetic diversity in our problem. You might be wondering, genetic 
diversity? What is he talking about? This is a computer program. Just have a 
little patience and you will understand what I mean soon enough</P>
<P class=content><IMG id=rightFloat 
src="The Real Intelligence Project - Genetic algorithms tutorial.files/crossover.png" 
width="60%">So, there we are having a population of potential solutions to our 
problem, all just generated randomly. None even close to being a good enough 
solution to what we want. But here is where, mimicking the mechanism of nature, 
we create a function called the evaluation function which plays the role of 
natural selection. This function assigns a fitness value to each and every 
chromosome in our population. This way we have a heuristic value telling us 
which solutions to prefer. Then trying to mimick nature's mechanism again we 
allow our chromosomes to reproduce. This is called recombination or crossover in 
genetic algorithm terms. We select the fittest chromosomes and some of the 
not-so fit just to keep the genetic diversity I mentioned above and allow them 
to reproduce. This, as we can see on the right, is done by setting the so called 
crossover points on the 2 parent chromosomes. We basically divide it into areas 
which will be transferred into the new children chromosomes. Then we perform the 
recombination by creating each child with combinations of their parent's DNA 
divided where we set the crossover points. In addition in typical genetic 
algorithms there is a very small random chance for some individual 'genes' of a 
chromosome to suddenly change their values taking some other legal value. This 
is called mutation and the random chance is the mutation rate. What happens next 
is that we evaluate again all the new children generated from recombination and 
mutation with our evaluation function. Then always keeping in mind the genetic 
diversity of our population we choose the fittest ones to go to the next 
generation along with some of the not so fit ones.</P>
<P class=content>This evolution keeps going on for generations, and as a result 
in each generation we have chromosomes which tend to be fitter and fitter 
matching our criteria of the perfect solution more and more. Unfortunately here 
is what we previously referred to as 'genetic diversity' comes into play. You 
see while this evolution continues for generations we reach a point where all 
recombinations and mutations of the parents produce offspring a lot worse than 
the parents and hence they do not go to the next generation. That is because we 
have reached a local optima, a point in the evolution of our species where the 
recombination of our genetic material just can't produce better results. This is 
a very important problem with genetic algorithms and which we will see in the 
source code example that is about to follow. There are ways out of course, such 
as detecting these local optima and injecting new genetic material into our 
population or implementing directed mutation.</P>
<P class=content>But let's see an actual source code example. For this tutorial 
I chose to create for you a genetic algorithm sudoku solver. It will showcase 
both the strengths and the weaknesses of genetic algorithms as we will very soon 
see, not to mention that for sudoku fans it will be pretty interesting. Of 
course in terms of speed and efficiency it can not even be remotely compared to 
any decent sudoku solver, since genetic algorithms have the big disadvantage of 
being slow and computationally expensive. So here is our representation of any 
sudoku puzzle in code: </P><PRE class=sourceCode style="FLOAT: right" width=50%>    int sudokuRepresentation[] = {
        5,3,X,      X,7,X,      X,X,X,
        6,X,X,      1,9,5,      X,X,X,
        X,9,8,      X,X,X,      X,6,X,
    
        8,X,X,      X,6,X,      X,X,3,
        4,X,X,      8,X,3,      X,X,1,
        7,X,X,      X,2,X,      X,X,6,
    
        X,6,X,      X,X,X,      2,8,X,
        X,X,X,      4,1,9,      X,X,5,
        X,X,X,      X,8,X,      X,7,9
};</PRE>
<P class=content>Wherever there is a X we consider it a variable and the other 
numbers are the given information about each sudoku. This particular one is 
taken directly from wikipedia's <A 
href="http://en.wikipedia.org/wiki/Sudoku">sudoku page</A>. Each solution is 
represented by an array of ints( a pointer to int in code). The size of that 
array is the number of unknowns in the sudoku puzzle. So for that particular 
puzzle above we would have a 51 integers array for our chromosome. Each one 
representing a potential sudoku solution.</P>
<P class=content>The classes which were made to represent these in the source 
code are two. One is of course the chromosome class, representing our 
chromosomes and the popoulation class which contains all the information about 
all our chromosomes and their genetic parameters, such as crossover points and 
mutation rate. As can be seen in the code box below the chromosome contains an 
evaluation function and its solution representation. On the other hand the 
population contains all of its chromosomes in a vector and its starting setup, 
meaning the initial sudoku puzzle configuration. In addition the population 
contains a roulette wheel. This as we will see is our selection mechanism to 
select chromosomes for reproduction</P><PRE class=sourceCode>class Chromosome
{
    public:
        int* representation;
        int size;
        int fitness;
        int penalty;

        //constructor and destructor
        Chromosome(int unknowns);
        ~Chromosome();
        //operator overloading just so we can assign chromosomes in the population
        Chromosome&amp; operator=(const Chromosome&amp; c);
        //the evaluation function
        void evaluate(int* startingSetup);
        //helper function to get the offset of the chromosome
        //when seen in the whole filled sudoku puzzle
        void getChromoOffset(int pos,int* setup,int &amp;offset);

};


class Population
{
    private:
        //our starting sudoku puzzle
        int* startingSetup;
        //the population count
        int populationNumber;
    public:
        //the actual chromosome population
        std::vector&lt;Chromosome*&gt; genePool;
        //this is our selection method
        //a roulette wheel selection
        std::vector&lt;int&gt; rouletteWheel;
        //constructor
        Population(int populationNumber,int* rules);
        //performs Selection of chromosomes, recombinations
        //and mutations and creates the next generation of solutions
        void selectAndRecombine(int crossoverpoints,int mutationRate,bool newMaterial,bool superMutation);
        //Returns the fittest chromosome in our population
        Chromosome* getFittest();
        //prints the solution to the sudoku puzzle that the
        //parameter chromosome reperesents
        void printSolution(Chromosome* chromo);
        //clears the given population gene pool
        //since memory leaks are bad
        void clearPool(std::vector&lt;Chromosome*&gt;&amp; a, int size);

};
</PRE>
<P class=content>But let us delve a little deeper into the tutorial's code. I 
will not show the evaluation function's code here since it is pretty simple, all 
it does is count the numbers the chromosome breaks the three sudoku rules and 
assign penalties. Each chromosome is given a penalty point for each rule broken 
and for each rule which it upholds fitness is added to it. I gave each rule 
equal fitness and penalty values since to tell the truth I am not that familiar 
with sudoku. Maybe some sudkoku experts think differently. If so please email me 
so I can correct it or even better change the macros which define the penalty 
and fitness values in the code yourself and see the results.</P>
<P class=content>Let's see now some snippets from the most important function in 
all of the tutorial, the function which performs selection, recombination and 
mutation and creates the next generation of solutions:</P><PRE class=sourceCode>  ...
 //evaluating the genePool
    for(int i = 0; i &lt; popSize; i++)
    {
        (genePool.at(i))-&gt;evaluate(startingSetup);
    }
  ...
  ...
  //creating the roulette wheel according
  //to the fitness of each chromosome
   for(int i =0 ; i&lt; popSize; i++)
    {
        if(!injectNewGeneticMaterial)
        {
            prFitness = cFitness;
            cFitness +=(genePool.at(i))-&gt;fitness;

            for(int j=prFitness/ratio;j&lt;cFitness/ratio;j++)
            {

                rouletteWheel.push_back(i);
            }
  ...
  ...
  //Choosing parents depending on their portion of the roulette wheel
  //random number from 0 to roulettesize-1
   Parent1 = genePool.at(     rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) )  );
   if(!injectNewGeneticMaterial)
   {
        //random number from 0 to roulettesize-1
        Parent2 = genePool.at(  rouletteWheel.at( int((rouletteSize*rand())/(RAND_MAX + 1)) )  );
   }
  ...
  ...
  //Performing recombination
    for(int s = 0; s&lt;= crossoverpoints; s++)
    {

		 if(s != crossoverpoints)
         {
             destination = Child1-&gt;representation;

             if(s%2 == 0)
                source = Parent1-&gt;representation;
             else
                source = Parent2-&gt;representation;

             memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));


             destination = Child2-&gt;representation;


              if(s%2 == 0)
                 source = Parent2-&gt;representation;
              else
                 source = Parent1-&gt;representation;
             
              memcpy(destination+offset,source+offset,(points.at(s)-offset)*sizeof(int));

              offset = points.at(s);
          }
          else
          {
               destination = Child1-&gt;representation;
                if(s%2 == 0)
                    source = Parent1-&gt;representation;
                else
                    source = Parent2-&gt;representation;
                
                memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
                
                destination = Child2-&gt;representation;
                if(s%2 == 0)
                    source = Parent2-&gt;representation;
                else
                    source = Parent1-&gt;representation;
                memcpy(destination+offset,source+offset,(chromoSize-offset)*sizeof(int));
            }
      }

      points.clear();
  ...

</PRE>
<P class=content>As can be seen in the first snippet we can see how each 
chromosome gets evaluated by invoking its evaluation function.</P>
<P class=content>Then a little later down in the code comes the second snippet. 
This shows how the roulette wheel is created. It is quite simple. Basically we 
get the whole population's fitness and get the total fitness's ratio to the 
RAND_MAX value(the maximum value that can be returned by rand(). Subsequently we 
assign a part of the roulette to each chromosome proportionate to their 
fitness's level when compared to the total fitness. That way all chromosomes can 
still be selected, but fitter individuals have a higher chance of doing 
so.<BR>Then in the third snippet is the actual recombination code. As we can see 
the 2 children are actually created by the 2 selected parents genetic code 
recombined in 's' crossover points, a number given as a parameter from the 
start.</P>
<P class=content>That was the essence of the code, there are some other details 
of course but you can see it for yourself by downloading the .rar file. What is 
important is that you understand the concept of a genetic algorithm.</P>
<P class=content>Let's see though how does the algorithm fare when running and 
trying to evolve the solution to a sudoku puzzle. As was already mentioned 
traditional genetic algorithms are really slow when compared to more 
conventional solving algorithms and especially in a sudoku puzzle's case which 
has only one and unique solution this applies even more. After some 
experimentation I concluded that a population of 2000 and 14 crossover points 
was a very nice genetic setup. The population size if of utmost importance since 
a small population does not have enough genetic material from which a good 
solution can be evolved. As for the number of crossover points this is a unique 
characteristic of the sudoku puzzle. The number of crossover points used in a 
typical genetic algorithm is 1-3. In our case though since a sudoku has only one 
and unique solution exchange of genetic material must be performed in as many 
parts as possible so as to avoid the local optima problem. Take a look below to 
see the main code of the tutorial where we can see the program's logic and how 
ti evolves the generations of our solutions.</P><PRE class=sourceCode>    Population pop(populationN ,(int*)sudokuRepresentation);

    int fitness = 0;
    int generations = 0;
    int mutation = 100;
    int samePenaltyCount = 0;
    int prPenalty = 999;
    int backTrackCount = 0;

    int penalty = 99;
    while(penalty &gt; 0 )
    {
        if(samePenaltyCount &gt; 15)
        {
            samePenaltyCount = 0;
            pop.selectAndRecombine(crossoverPoints,mutation,true,true);//100/32765 seems to be nice
            backTrackCount++;
        }
        else
            pop.selectAndRecombine(crossoverPoints,mutation,false,false);



        printf("Best Fitness in generation %d is %d  with backtracks: %d \n\r",generations,(pop.getFittest())-&gt;fitness,backTrackCount);
        penalty = (pop.getFittest())-&gt;penalty;

        if(penalty == prPenalty)
            samePenaltyCount++;
        else
            samePenaltyCount = 0;

        prPenalty = penalty;

        printf("The penalty of the fittest one is %d \n\r",penalty);
        pop.printSolution(pop.getFittest());
        generations++;
    }


</PRE>
<P class=content>One can easily spot the option for backtracking. That is if the 
algorithm is stuck at the same fitness level for 15 generations the algorithms 
performs a super mutation hence almost totally changing the population. I count 
these as backtracks. Below is the output:</P><PRE class=sourceCode>Best Fitness in generation 57 is 4860  with backtracks: 0
The penalty of the fittest one is 0
5  3  4     6  7  8     9  1  2
6  7  2     1  9  5     3  4  8
1  9  8     3  4  2     5  6  7

8  5  9     7  6  1     4  2  3
4  2  6     8  5  3     7  9  1
7  1  3     9  2  4     8  5  6

9  6  1     5  3  7     2  8  4
2  8  7     4  1  9     6  3  5
3  4  5     2  8  6     1  7  9


Process returned 0 (0x0)   execution time : 40.859 s
</PRE>
<P class=content>This is the result of a run of the algorithm. This is a good 
run, in fact one of the best runs. There were no backtracks and it found the 
solution in 40 seconds. Unfortunately this is not the typical run. In a typical 
run it might do 1 backtrack, or even 2. That is because the algorithm gets to a 
point where it just can't improve the chromosomes anymnore. Moreover in some 
very hard sudokus it might not be able to find a solution in a sufficient amount 
of time and might need to do many backtrackings. Backtracking is not something 
that genetic algorithms usually do. I added it just so it can solve it faster. 
There are other more advanced genetic techniques such as directed mutations 
which would target the genes which cause the problem whenever we get suck in a 
local optima. Through these mutations we would be able to change the problematic 
genes until they take the form we want. Other mor exotix ideas involve wars 
between different populations, parallel genetic evolution (running on many 
processors) e.t.c.</P>
<P class=content>Of course such techniques are out of the scope of this 
tutorial. This tutorial's goal was to give an introduction to genetic algorithms 
and give an educating, comprehensive and interesting example of their use. I 
hope that you found it usefull and that something was learned by reading this 
tutorial. Remember that a sudoku puzzle is not the best example to give for 
genetic algorithms since it has only one solution but it is good enough to 
demonstrate a practical example of genetic algorithms. You can find the source 
code <A 
href="http://www.realintelligence.net/Files/GeneticAlgosTutorial.rar">here</A>. 
I hope you find it usefull and please email me at lefteris *at* realintelligence 
*dot* net for any comments/suggestions or constructive criticism. See you in the 
next tutorial!</P><!-- InstanceEndEditable --></LI></DIV></DIV></DIV>
<DIV id=leftBCorner></DIV>
<DIV id=bottomWrapper></DIV>
<DIV id=rightBCorner></DIV></DIV></DIV><!-- InstanceEnd --></BODY></HTML>
